// LeetCode 主站 Problem Nr. 279: 完全平方数

/*
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
	输入：n = 12
	输出：3
	解释：12 = 4 + 4 + 4
示例 2：
	输入：n = 13
	输出：2
	解释：13 = 4 + 9

提示：
	1 <= n <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"
)

func numSquares(n int) int {
	// return method1(n)
	return 0
}

func method1(n int) int {
	queue := []int{0}
	level := 0
	calculated := make(map[int]bool, 0)

	for len(queue) > 0 {
		size := len(queue)
		level++

		for i := 0; i < size; i++ {
			e := queue[0]
			queue = queue[1:]

			for j := 1; e+j*j <= n; j++ {
				if e+j*j == n {
					return level
				}

				if !calculated[e+j*j] {
					queue = append(queue, e+j*j)
					calculated[e+j*j] = true
				}
			}
		}
	}

	return level
}

func method2(n int) int {
	queue := []int{0}
	level := 0
	quit := false
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			e := queue[0]
			queue = queue[1:]
			if e == n {
				quit = true
				break
			}
			for j := 1; e+j*j <= n; j++ {
				queue = append(queue, e+j*j)
			}
		}
		if quit {
			return level
		}
		level++
	}
	return level
}

func main() {
	fmt.Println(method1(7168))
}
